We study the possible growth rates of the Kolmogorov complexity of initialsegments of sequences that are random with respect to some computable measureon $2^\omega$, the so-called proper sequences. Our main results are as follows:(1) We show that the initial segment complexity of a proper sequence $X$ isbounded from below by a computable function (that is, $X$ is complex) if andonly if $X$ is random with respect to some computable, continuous measure. (2)We prove that a uniform version of the previous result fails to hold: there isa family of complex sequences that are random with respect to a singlecomputable measure such that for every computable, continuous measure $\mu$,some sequence in this family fails to be random with respect to $\mu$. (3) Weshow that there are proper sequences with extremely slow-growing initialsegment complexity, that is, there is a proper sequence the initial segmentcomplexity of which is infinitely often below every computable function, andeven a proper sequence the initial segment complexity of which is dominated byall computable functions. (4) We prove various facts about the Turing degreesof such sequences and show that they are useful in the study of certain classesof pathological measures on $2^\omega$, namely diminutive measures and trivialmeasures.
展开▼
机译：我们研究了序列初始段的Kolmogorov复杂度的可能增长率，该序列相对于$ 2 ^ \ω$的某些可计算量度（即所谓的适当序列）是随机的。我们的主要结果如下：（1）我们证明，当且仅当$ X $是随机的，且适当时，适当序列$ X $的初始片段复杂度由一个可计算的函数（即$ X $是复杂的）从下面限制。关于一些可计算的，连续的度量。 （2）我们证明先前结果的统一形式不能成立：存在一个复杂序列序列，该序列相对于单个可计算量度是随机的，从而对于该可计算的连续量度，每个序列中的某个序列不能相对于$ \ mu $是随机的。 （3）我们表明存在适当的序列，其初始段复杂度增长极慢，也就是说，存在一个适当的序列，其初始段复杂度经常无限地低于每个可计算函数，甚至是一个适当的序列，其初始段复杂度占主导地位所有可计算功能。 （4）我们证明了有关此类序列的图灵度的各种事实，并表明它们可用于研究$ 2 ^ \ omega $上某些类别的病理测量，即缩小测量和琐碎测量。
展开▼
